//
// Created by zs on 2022/7/20.
//

#include <queue>

using namespace std;

/**
 * Definition for a binary tree node.
 **/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q)return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    // 方法一：递归
    bool isSymmetric(TreeNode *root) {
        return check(root, root);
    }

    // 方法二：迭代
    bool check1(TreeNode *u, TreeNode *v) {
        queue<TreeNode *> q;
        q.push(u);
        q.push(v);
        while (!q.empty()) {
            u = q.front();
            q.pop();
            v = q.front();
            q.pop();
            if (!u && !v)continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left);
            q.push(v->right);

            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric1(TreeNode *root) {
        return check(root, root);
    }
};

int main() {
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(3);
    TreeNode *node6 = new TreeNode(4);

    TreeNode *node1 = new TreeNode(2, node3, node4);
    TreeNode *node2 = new TreeNode(2, node6, node5);

    TreeNode *root = new TreeNode(1, node1, node2);

    Solution solution;
    printf("%d", solution.isSymmetric1(root));
    return 0;
}